\documentclass[a4paper,11pt]{article}
\usepackage{techrep-dc-uel}

\usepackage[brazil]{babel}
%\usepackage[latin1]{inputenc}
\usepackage{verbatim}
\usepackage{pstricks}
\usepackage{psfrag}
\usepackage{epsfig}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{lscape}
\usepackage{url}
\usepackage{amssymb}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage[utf8]{inputenc}
\usepackage{picinpar}
\usepackage{textcomp}

\begin{document}


% Author list for the cover page (without affiliations).
\TRAuthor{Edgar Tomita \and Josue Crispim}

% Author list for the cover page (with affiliations).
\TRAuthorAffiliation{}

% Title for cover page (use \\ to force line breaks).
\TRTitle{Autômatos finitos e suas aplicações}

\TRMakeCover

\begin{abstract}
 
Autômatos finitos são amplamente utilizados dentro da ciência da computação, a maior parte dos compiladores e sistemas processadores de linguagem usam 
autômatos finitos. Não estando restrito só a ciência da computação tem grande utilidade para a biologia e engenharia elétrica além de sua grande importância 
no estudo de linguagens naturais. Os autômatos finitos estão divididos em dois grupos os dos reconhecedores que são ser os determinísticos ou não determinísticos e os 
transdutores que são ser as máquinas de Moore e Mealy. Eles reconhecem linguagens regulares ou do tipo 3 segundo a hierarquia de Chomsky. Ao longo deste trabalho 
iremos revisar a teoria dos autômatos, das máquinas reconhecedoras e transdutores, assim como uma abordagem prática do uso dos autômatos finitos na bioinformática 
para a análise de sequências e para o uso em modelos de predição e por último 

\end{abstract}

\section{Introdução}
Autômato finito é uma abstração computacional que é usada amplamente em inúmeras áreas como \textit{design} de circuitos digitais para 
sistemas de modelagem, comunicação de protocolos, linguagens de programação e \textit{design} de compiladores. Processadores de texto freqüentemente usam autômatos finitos é uma das 
ferramentas mais utilizadas na World Wide Web, na busca de uma ou um conjunto de palavras. 

Segundo \cite{Lawson} o termo ‘autômato finito’ descreve uma classe de modelos computacionais que são caracterizados por terem um número finito de estados. 
Em particular os autômatos finitos formam uma classe com linguagens restritas, devido essa restrição eles se tornam mais fáceis de serem manipulados.

Divididos em dois grupos os das máquinas reconhecedoras que reconhecem a sua entrada e usam seus estados para sinalizar o resultado para sinalizar o 
resultado para o mundo externo. E os transdutores que geram uma saída baseada em uma entrada ou estado utilizando ações. Amplamente utilizado para aplicações 
de controle. Dentro dos transdutores temos as máquinas de Moore e Mealy.

Iremos estudar a teoria dos autômatos finitos em 2, então entraremos em detalhes, nos grupos que formam os autômatos finitos primeiramente com os reconhecedores 
estudando os autômatos finitos determinísticos em 3 e então os autômatos finitos não determinísticos em 4 assim como algumas operações nesse grupo.

Em 8 iremos estudar a teoria por traz transdutores, as máquinas de Moore e Mealy, assim como algumas operações realizadas nesse grupo. 

Também iremos ver em 9 a aplicação do que foi estudado, para algumas tarefas na manipulação de dados e modelos de predição utilizados na bioinformática como 
comparação de sequências 5.1, detecção de padrões dentro da sequência 5.2 e Detecção de regiões reguladoras no gene 5.3. e finalizando em 10 a aplicação de autômotos em jogos. 

%Daqui para frente vai o conteudo
\section{Autômatos finitos}

Em considerações gerais os reconhecedores são sistemas em que eles tem como entrada uma palavra  $\alpha$ $\in$ $\Sigma$, será 
lido símbolo por símbolo até o final da palavra, caso não encontre erros antes, e no último símbolo da palavra o autômato estiver 
no estado de aceitação, a palavra é aceita, o oposto ela é rejeitada. Os reconhecedores contêm um conjunto de estados finitos e o 
seu “controle” se desloca para outro estado de acordo com a “entrada” externa. 

\textit{Exemplo 1.} Autômato reconhecedor simples.
 
Um interruptor liga/desliga que memoriza o estado “ligado” e “desligado”, e permite que o usuário mude de estado diferente 
do que está através de um botão. Se o interruptor estiver no estado "ligado", após pressionar o botão levará o estado para 
“desligado”, se estiver no "desligado", e pressionar o botão irá para o "ligado".\cite{hp}

\begin{figwindow}[2, c,{\includegraphics[height=7cm,width=\textwidth]{automatofinito.jpg}}, {A figura 1 apresenta o autômato finito para o interruptor. Os estados são apresentados pelos círculos 
    (ligado e desligado) e os arcos apresentam as “entradas”, representado as influências externas (pressionar). A idéia é 
     de que o sistema mude de estado toda vez que a entrada pressionar é recebida.}]
\end{figwindow}
O estado “inicial” em um autômato é indicado pela seta início. Muitas vezes é necessário indicar um ou mais estados como sendo “finais” 
ou de “aceitação”. Este estado é indicado por um círculo duplo.

Uma das formas de representação de um autômato é de diagrama de estado de transição ou grafo. Que é um grafo orientado 
onde os nos são os estados e as arestas nomeadas com os símbolos representam a mudança de estado ou transição causada 
pela leitura do terminal segundo\cite{AutomatoL1}.

\textit{Exemplo 2.} Constantes Decimais.\cite{AutomatoL1}

L o conjunto de decimais constantes tem o alfabeto $\Sigma$ = $\Delta$ $\cup$ \{0,$\bullet$\} onde delta = {0,1,2,3,4,5,6,7,8,9} é um digito
diferente de 0.
 
\begin{figure}[!htb]
    \begin{center}

       \includegraphics[height=7cm,width=\textwidth]{Diagramaetabd.jpg}

    \end{center}
    \caption{Diagrama de estado ou grafo (esquerda) e tabela (direita) para constantes decimais (exemplo 1)}
    \label{fig:programa}
\end{figure}

Dado uma palavra 0 $\bullet$ 2 $\bullet$, o autômato anda pelos estados $q_{0}, q_{2}, q_{3}, q_{4}$. No último estado, uma vez que  
nenhuma transição permita a leitura de um simbolo $a$ $\bullet$, o cálculo pára antes da palavra seja lida por inteiro. Como uma
consequ\^{e}ncia, a palavra não é aceita. Por outro lado, a entrada 0 $\bullet$ 21 seria ser aceita.

Se quisermos modificar a linguagem para as contantes 305 $\bullet$ terminando com um decimal o e um ponto serem aceitas, o $q_{3}$ também tem que
ser marcado como estado final \cite{AutomatoL1}.

\section{Autômatos finitos determinísticos}
Quando o autômato não pode estar em mais de um estado em qualquer momento, se diz que é determinístico\footnote{
O termo “determinístico” se refere ao fato de que, para cada entrada, existe um e somente um estado ao qual o 
autômato pode transitar a partir de seu estado.\cite{hp} }. 
Pode ser definido simplesmente por AFD ou DFA.

O autômato finito determinístico é uma 5-upla onde:

\begin{enumerate}
	\item{$\Sigma$ representa um conjunto finito de símbolos de entrada;}
	\item{Q conjunto de estados possíveis do autômato;}
	\item{$\delta$ função de transição;}
	\item{$q_{0}$ estado inicial;}
        \item{F conjunto de estados finais.}
\end{enumerate}

Assim, temos uma “tupla de cinco elementos”:

\begin{center} 
A = ($\Sigma$, Q, $\delta$, $q_{0}$, F )\end{center}

Todo autômato finito tem pelo menos um estado, que é o estado inicial $q_{0}$. Os símbolos de entrada são representados pelo alfabeto $\Sigma$ 
e a função de transição $\delta$ especifica o movimento, por exemplo quando  aparece $\delta(q,a) = r$, significa 
que a maquina M que está no estado $q$ lê a e vai para $r$ caso $\delta(q,a)$ é indefinido o autômato para.


O autômato processa uma palavra não vazia x com uma serie de movimentos. Pegando $x = ab$, lendo o primeiro caractere, o primeiro passo $\delta(q_{0},a) = q_{1}$ 
leva ao estado q1, então para o q2 pelo segundo passo $\delta(q_{1},b) = q_{1}$. Podemos também escrever de forma reduzida $\delta(q_{0},ab) = q_{2}$ que diz lendo
a palavra $ab$ a maquina move para o estado $q_{2}$.\cite{AutomatoL1}

Um caso especial e a palavra vazia. Que não assume mudanças de estado:

\begin{center}
$\forall q \in Q \colon \delta(q,\varepsilon) = q $ 
\end{center}

Seguindo temos que o domínio da função  transição é $Q \texttimes \Sigma \textasteriskcentered$ e a definição é:

\begin{center}  
$\delta(q,ya) = \delta(\delta(q,y),a)$, onde $a \in \Sigma$ e $y \in \Sigma \textasteriskcentered$
\end{center}

Olhando o autômato como grafo, se $\delta(q,y) = q'$, então, e somente então, existe um caminho do no $q$ para o no $q’$, 
tal que a concatenação das arestas tem as palavra $y$. Dizemos que $y$ é um rotulo do caminho.

A palavra x e reconhecida ou aceita por um autômato se é um rotulo de um caminho do estado inicial até o estado final, $\delta(q_{0},x) \in F$.

A linguagem reconhecida ou aceita pelo autômato M é:

\begin{center}  
$L(M) = x \in \Sigma \textasteriskcentered \{x$ $e$ $reconhecida$ $por$ $M \}$
\end{center}

Dois autômatos são equivalente se eles aceitam a mesmo linguagem.

O autômato processa uma palavra não vazia com uma série de movimentos e pode ser visto como 
sendo uma máquina composta por três partes:\cite{mene}

\begin{enumerate}
	\item{Fita: contém a informação a ser lida;}
	\item{Unidade de Controle: reflete o estado da máquina. A unidade de leitura acessa uma célula da 
	fita de cada vez. Sempre da esquerda para a direita}
	\item{Função de transição ou Programa: comanda as leituras definindo o estado da máquina.}
\end{enumerate}

A fita é dividida em célula e é finita. Cada célula armazena um símbolo que pertencem a entrada. Não existe nenhuma memória auxiliar e 
também não é possível gravar sobre a fita. A informação a ser coletada ocupa toda a fita.

Na unidade de controle, os estados são predefinidos e em um número finito. O símbolo é lido uma célula de cada vez. Depois de lido a 
unidade de controle é deslocada para a direita a fim de ler o próximo símbolo, assim sucessivamente até o fim da 
fita.

\begin{figwindow}[2, c, {\includegraphics[height=7cm,width=\textwidth]{fita.png}}, { Fita representando um autômato finito.}]
\end{figwindow}

O programa define o novo estado do autômato após a leitura. Como não há nenhuma memória auxiliar, utiliza-se o 
conceito de estado para armazenar as informações.

\subsection{Função programa estendida}

Dado $\delta(q,ya) = \delta(\delta(q,y),a)$, um DFA, em [4] a função programa estendida é definida por:

$\delta$ : $Q$  $\texttimes$  $\Sigma \textrightarrow Q $

é a função programa : $Q \texttimes \Sigma \textrightarrow Q$estendida para palavra, definida por indução:

$\delta(q,\varepsilon)$ = q

$\delta(q,wa)$  = $\delta(\delta(q,a), w)$ 


\subsection{Autômatos vacuosos}
Se o conjunto de estados finais dos autômatos for vazio a linguagem gerada também é vazia, ou seja, $L = 0$.Mas existem AFDS com 
estados finais  que geram a linguagem vazia, para acontecer isso não poderá existir nenhum caminho que comece no estado inicial  e 
termine no estado final. Todo AFD que a linguagem for vazia é designado por AFD vacuoso.

\subsection{Estados acessíveis, produtíveis e inúteis}
Em um autômato um estado e acessível se ele começa no estado inicial $q_{0}$ e termina em um estado $q$. Um estado $q$ é produtivo se existe um 
caminho entre ele e o estado final. Um estado $q$ é inútil se ele não for acessível e não for produtivo.



\section{Autômatos Finitos Não-Determinísticos}

O autômato finito não-determinístico, ou simplesmente NFA ou AFND, pode estar em vários estados ao mesmo tempo com isso fica mais fácil a leitura 
do grafo do autômato e também permite definições mais curtas. 
Diferente da AFD, a função de transição da NFA não define necessariamente o próximo estado, porém fornece uma 
lista de estado para as quais a transição poderia ser feita. A lista tem um número $\geq$ 0.

Enquanto a NFA aceita uma cadeia se o último estado atingido é final, na NFA a cadeia é aceita se existe uma 
sequência de escolhas onde o último estado atingido é final.

O autômato finito não-determinístico é uma 5-upla onde:

\begin{enumerate}
	\item{$\Sigma$ representa um conjunto finito de símbolos de entrada;}
	\item{Q conjunto finito de estados;}
	\item{$\delta$ função de transição. Recebe um estado Q e um símbolo do alfabeto e retorna um F. 
No NFA é um conjunto de estados enquanto que no NFA é um único estado;}
	\item{$q_{0}$ estado inicial;}
	\item{F conjunto (subconjunto de Q) de estados finais.}
\end{enumerate}

Assim, temos uma “tupla de cinco elementos”:

\begin{center} A = ($\Sigma$, Q, $\delta$, $q_{0}$, F )\end{center}

\textit{Exemplo 3}\cite{AutomatoL1}

Seja a cadeia de entrada ababa e a NFA dado pelo diagrama da figura:

\begin{center}
\begin{figwindow}[2, c, {\includegraphics[height=7cm,width=\textwidth]{ExemploNFA.png}}, {Diagrama que representa o autômato finito não-determinístico}]
\end{figwindow}\end{center}

A cadeia é aceita, pela sequência de estados $q_{0}, q_{1}, q_{1}, q_{1}, q_{1}, q{2}$. A sequência de estado poderia ser também $q_{0}, 
q_{1}, q_{1}, q_{1}, q_{1}, q_{1}$ que não leva a um estado final. Há uma sequência que é interrompida, $q_{0}, q_{1}, q_{1}, q_{2}$, que 
não prevê uma transição com o segundo b. Mesmo com esses casos o autômato é aceito, porque há um caminho certo.

Este afnd aceita a linguagem das cadeias (de comprimento maior ou igual a 2), cujo
primeiro e último símbolos são a, sendo os restantes quaisquer. (Compare este afnd com
o afd de um dos exemplos anteriores, que aceita a mesma linguagem.)

Temos, para a mesma cadeia ababa de entrada,

(q0, ababa) $\vdash$ (q1, baba) $\vdash$ (q1, aba) $\vdash$ (q1, ba) $\vdash$ (q1, a) $\vdash$ (q2, e)

e, portanto, ababa I L(M). Temos também o "caminho errado"

(q0, ababa) $\vdash$ (q1, baba) $\vdash$ (q1, aba) $\vdash$ (q1, ba) $\vdash$ (q1, a) $\vdash$(q1, e)

que leva à configuração não final (q1, e), e não permite nenhuma conclusão.

Cadeias como bab e abab não levam a configurações finais e não são aceitas. Da

configuração (q0, bab) nenhuma configuração é atingível; para abab temos:

(q0, abab) $\vdash$ (q1, bab) $\vdash$ (q1, ab) $\vdash$ (q1, b) $\vdash$ (q1, e)

Adicionalmente, temos um outro caminho

(q0, abab) $\vdash$ (q1, bab) $\vdash$ (q1, ab) $\vdash$ (q2, b)

que também não atinge nenhuma configuração final. Assim, as cadeias bab e abab não

são aceitas e não fazem parte de L(M).            

\textit{Exemplo 4}\cite{AutomatoL1}

Considere o afnd M da Fig. 4.5. M aceita cadeias da forma c y c, onde c
pode ser a ou b e y pode ser qualquer cadeia de a's e b's.
A cadeia ababa  = c×y×c = a×bab×a é aceita por M, através da sequência de configurações
abaixo, em que a primeira e a última transições são realizadas através de transições-e.

(A, ababa)   M lê e e adivinha que c=a

$\vdash$ (B, ababa)            M lê a e confere que c=a

$\vdash$ (C, baba)             M lê b

$\vdash$ (C, aba)              M lê a e adivinha que este a faz parte de y

$\vdash$ (C, ba)               M lê b

$\vdash$ (C, a)                M lê a e  adivinha que este a é o último c

$\vdash$ (D, e)                M lê e e adivinha que a cadeia acabou

$\vdash$ (I, e)                M aceita

\begin{center}
\begin{figwindow}[2, c, {\includegraphics[height=7cm,width=\textwidth]{exemploAFND.png}}, {AFND para o exemplo}]
\end{figwindow}
\end{center}
Todas as configurações atingíveis (caminhos certos e errados) estão indicadas abaixo:

(A, ababa)

$\vdash$ (B, ababa)

. $\vdash$ (C, baba)

. $\vdash$ (C, aba)

. $\vdash$ (C, ba)

. . $\vdash$ (C, a)

. . $\vdash$ (C, e) -- não aceita

. . $\vdash$ (D, e)

. . $\vdash$ (I, e) -- ok! aceita!

. $\vdash$ (D, ba)

. $\vdash$ (I, ba) -- bloqueado

$\vdash$ (F, ababa) -- bloqueado

\subsection{Função programa estendida}

Dado A = ($\Sigma$, Q, $\delta$, $q_{0}$, F ), um NFA, em [4] a função programa estendida é definida por:
$\delta$ : $2Q$ $\texttimes$ $\Sigma$ $\textrightarrow$ $2Q$
é a função programa $\delta$ : $Q$ $\texttimes$ $\Sigma$ $\textrightarrow$ $2Q$ estendida para palavra e por indução definida como:

$\delta$ $(P, \varepsilon)$ = P

$\delta$ (q, aw) = $\delta$($\cup$ q $\varepsilon$ P $\delta$ (q, a), w) 

	Assim, para um dado conjunto de estados ($q_{1}, q_{2}...q_{n}$) e para um dado símbolo a:

$\delta$(\{$q_{1}, q_{2}...q_{n}$\}, a) = $\delta$ ($q_{1}$, a) u $\delta$($q_{2}, a) u...u \delta(q_{n}, a)$

	A linguagem aceita por NFA M, denotada por ACEITA(M) ou L(M), é o conjunto de todas as palavras pertencentes a $\Sigma$ tais que existe um caminho alternativo que aceita ou rejeita a palavra, ou seja:

ACEITA(M) = \{ w | existe q $\varepsilon$ $\delta$($q_{n}, w)$ tal que q $\epsilon$ F\}

	REJEITA(M), é o conjunto das palavras pertencentes a $\Sigma$ rejeitadas por todos os caminhos alternativos de M, a partir de $q_{0}$).

\section{Equivalência entre AFD e AFN}

Há uma equivalência entre as duas classes de autômatos: os determinísticos e não-determinísticos.

\textit{Prova:} 

A ideia é mostrar que a partir de um AFN M qualquer, é possível construir um AFD $A’$. O algoritmo demonstra a conversão de um AFN qualquer em um 
AFD equivalente. O objetivo é a construção de estados de $A’$ tal que simule as diversas combinações de estados alternativos de M.\cite{mene}

Seja $A'$ = ($\Sigma$, Q, $\delta$, $q_{0}$, F ) um AFN qualquer e $A’$ = ($\Sigma$, Q', $\delta$', \textless$q_{0}$\textgreater, F' ) um AFD construído a parti de A:

\begin{enumerate}
	\item{A': todas as combinações possíveis, sem repetições, de estados de $Q$ as quais são denotados por $<q_{1} q_{2}....q_{n}>$ sendo que $q_{i}$
          pertence a $Q$ e $i \geqq 1$. A ordem dos elementos não distingue mais combinações, ou seja, $<q_{u}q_{v}> = <q_{v}q_{u}>$;}     
	\item{$\delta$’: tal que $\delta$’($<q_{1}....q_{n}>$, a) =$<p_{1}....p_{n}>$se, e somente se, $\delta$($\{q_{1}....q_{n}\}$, a) = ($\{p_{1}....p_{m}\}$ 
         Ou seja, a imagem de todos os caminhos alternativos de $A$ é representado por $M’$;}
 	\item{F: conjunto de estados $<q_{1} q_{2}....q_{n}>$ pertences a $Q’$ tal que alguma componente $q_{i}$ pertence a F, i $\geqslant$ 1.}   
\end{enumerate}

A demonstração de que $A’$ simula o processamento de $A$ é por indução da tamanho da palavra. Supondo que $w$ é uma palavra qualquer de $\Sigma$, deve-se mostrar que:

\begin{center}
$\delta$’($<q_{0}>$, w) = $<q_{1}....q_{u}>$ se, e somente se, $\delta$’($q_{0}$, w) = $q_{1}....q_{u}$ 
\end{center}

\begin{enumerate}
	\item \textit{Base de indução}.Seja w tal que | w | = 0. Então:$\delta$’($<q_{0}>, \epsilon)$ = $<q_{0}>$se, e somente se $\delta$’($q_{0}, \epsilon)$ = $q_{0}$
	\item{\textit{Hipótese de indução}.Seja um w tal que | w | = n e n $\geqslant$ 1 Suponha verdadeiro que:
$\delta$’($<q_{0}>$, w) = $<q_{1}....q_{u}>$ se, e somente se $\delta$($q_{0}$, w) = $<q_{1}....q_{u}>$
}
 	\item{\textit{Passo de indução}.Seja um w tal que | wa | = n + 1 e n $\geqslant$ 1 Suponha verdadeiro que:
$\delta$’($<q_{0}>$, w) = $<p_{1}....p_{u}>$se, e somente se $\delta$($q_{0}$, w) = $p{1}....p_{u}$ o que equivale:
$\delta$’($<q_{0}>$, w) = $<p_{1}....p_{v}>$ se, e somente se $\delta$’($\{q_{1}....q_{u}\}$, w) = $<p{1}....p_{u}>$
o que é verdadeiro, por definição de $\delta$’.
}   
\end{enumerate}

Portanto, $A$’ simula $A$ para qualquer w pertencente a $\Sigma$.

\section{Autômato Finito com Movimentos Vazios}

Trata-se de uma generalização dos modelos de máquinas não-determinísticas. Uma transição sem leitura de um símbolo na 
fita caracteriza o movimento vazio. Uma das vantagens, está no fato de facilitar demonstrações e construções relacionados a autômatos.

Em autômatos Finitos, a facilidade de movimentos vazios não melhora o reconhecimento de linguagens. Qualquer Autômato Finito com Movimentos 
Vazios pode ser simulado por um Autômato Finito Não-Determinístico.

O autômato finito não-determinístico com movimentos vazios, conhecido como AFN$_{\epsilon}$ ou AF$_{\epsilon}$ é uma 5-upla, onde:

\begin{enumerate}
	\item{$\Sigma$ representa um conjunto finito de símbolos de entrada;}
	\item{Q conjunto finito de estados possiveis;}
	\item{$\delta$ função de transição D:Q$\texttimes(\Sigma \cup \{_{\epsilon}\} \textrightarrow 2_{Q}$}
	\item{$q_{0}$ estado inicial;}
	\item{F conjunto (subconjunto de Q) de estados finais.}
\end{enumerate}

Assim, temos uma “tupla de cinco elementos”:

\begin{center} A = ($\Sigma$, Q, $\delta$, $q_{0}$, F )\end{center}


\section{Minimização de autômatos}
A ideia da minimização de autômatos, é gerar um autômato finito equivalente com o menor número de estados possíveis. 
Entretanto, a minimização não garante um custo menor na implementação.

O autômato minimizado, chamado de Autômato Finito Mínimo, é único a menos que seja um isomorfismo. Por exemplo, se 
dois autômatos aceitam uma linguagem, ao serem minimizados terão o mesmo Autômato Finito Mínimo

A definição de um Autônomo Mínimo é descrito por como: Uma linguagem regular $L$ é AFD,$A$ = ($\Sigma$, Q, $\delta$, $q_{0}$, F ) tal que $ACEITA(M) = L$ e 
que para qualquer outro AFD $A'$ = ($\Sigma$, Q, $\delta$, $q_{0}$, F ), tal que ACEITA(M) = $L$, tem-se que \#$Q'^{3}$ \#$Q$.\cite{mene}

Para minimizar um autômato deve-se respeitar:

\begin{enumerate}
	\item{O Autômato é determinístico;}
	\item{Não possui estados inacessíveis;}
	\item{Função programa total. São previstas transições para todos os símbolos do alfabeto a partir de 
         qualquer estado.}
\end{enumerate}

Caso algum desses casos não seja satisfeita não é possível realizar a minimização a menos que os problemas 
sejam corrigidos.

O algoritmo proposto por [1] é descrito como:
A partir de um AFD, $A$ = ($\Sigma$, Q, $\delta$, $q_{0}$, F ) que satisfaz todas as regras para minimização de um autômato. 
Os passos para do algoritmo são os seguintes:

\begin{enumerate}
	\item{Tabela. Relacionar os estados distintos através de uma tabela, onde cada par de estados ocorre somente uma vez, como na figura: 
\begin{figwindow}[2, c, {\includegraphics[height=7cm,width=\textwidth]{tabelaestadosminimizacao.png}}, {tabela com os estados minimizados}]
\end{figwindow}
} 
	\item{Marcação dos estados trivialmente não-equivalentes. Marcar os pares do tipo {estado final, estado não-final}. 
        Estados finais não são equivalentes aos estados não-finais.}
	\item{Marcação dos estados não equivalentes. Para cada símbolo a pertencente ao alfabeto e para cada par $(q_{u}, a)$, 
        suponha que $\delta(q_{u}, a) = p_{u}$ e $\delta(q_{v}, a) = p_{v}$ e:
	 \begin{enumerate}
	\item{Se $p_{u} = p_{v}$, então ambas são equivalentes para o símbolo a e não deve ser marcado;} 
	\item{Se $pu \neq pv$ e o par   $\{p_{u}, p_{v}\}$ não está marcado, então inclui-se $\{q_{u}, q_{v}\}$  é incluso em uma lista a partir de  $\{p_{u}, p_{v}\}$ para análise;}
	\item{Se $p_{u} \neq pv$ e o par  $\{p_{u}, p_{v}\}$ está marcado, então:
        \begin{enumerate}
	\item{$\{q_{u}, q_{v}\}$ não é equivalente, portanto é marcado;} 
	\item{se $\{q_{u}, q_{v}\}$ encabeça uma lista de pares, marcar todos os pares da lista e recusivamente, se algum par da lista encabeça outra lista;}
        \end{enumerate} 
        }
        \end{enumerate}
         }
       \item{Unificação dos estados equivalentes. Podem ser unificados os estados dos pares não marcados da seguinte maneira:
       \begin{enumerate}
	\item{são unificados em um único estado não-final os pares de estados não-finais equivalentes;} 
	\item{são unificados em um único estado final os pares de estados finais equivalentes;}
	\item{o estado unificado é inicial se alguns dos estados equivalentes é inicial;}
        \end{enumerate} 
       }
       \item{Exclusão dos estados inúteis. São excluídos os estados inúteis. Um estado q é inútil se é não-final e não se atinge ao estado final através dele.}

\end{enumerate}
\begin{figwindow}[2, c, {\includegraphics[height=7cm,width=\textwidth]{automatoaseminimizado.png}}, {Autômato Finito a ser minimizado}]
\end{figwindow}
\section{Máquinas de Moore e de Mealy}

A Máquina de Moore possui uma 
função que gera uma palavra de saída 
(que pode ser vazia) para cada estado da 
máquina. Esta saída só depende do 
estado atual da máquina.

Já a Máquina de Mealy é um 
Autômato Finito modificado de forma a 
gerar uma palavra de saída para cada 
transição entre os estados. Neste tipo de 
máquina de estados estas palavras de 
saída dependem do estado atual e do 
valor das entradas. 

Definições formais: 
 
Uma  Máquina de Mealy  M é 
autômato finito determinístico com 
saídas associadas às transições e pode 
ser representada formalmente pela 
sêxtupla M = ($\Sigma$, Q, $\delta$, $q_{0}$, F , $\Delta$), onde: \cite{Maq}

\begin{enumerate}
	\item{$\Sigma$ é um alfabeto de símbolos de entrada.} 
	\item{Q é um conjunto de estados possíveis do autômato, o qual é finito.}
	\item{$\delta$ é a função programa ou de transição}
        \item{$q_{0}$ é o estado inicial do autômato,tal que q0 é elemento de $Q$ }
        \item{F é um conjunto de estados finais tal que F está contido em Q.}
	\item{$\Delta$ é um alfabeto de símbolos de saída.}
        \end{enumerate} 

 O processamento de uma Máquina 
de Mealy para uma dada entrada w 
consiste na aplicação sucessiva da 
função programa para cada símbolo de 
w (da esquerda para a direita), até 
ocorrer uma condição de parada. Caso a 
saída da função programa seja uma 
palavra vazia, nenhuma gravação é 
realizada, ou seja, a cabeça da fita não se 
move. Porém se todas as transições de 
uma determinada máquina de Mealy 
gerarem saídas vazias, então esta se 
comporta  como um Autômato Finito.

Já uma  Máquina de Moore  M, 
como dito anteriormente, é um 
Autômato Finito Determinístico com 
suas saídas associadas aos estados. É 
representada formalmente por uma 
septupla  M = ($\Sigma$, Q, $\delta$, $q_{0}$, F , $\Delta$, $\delta$S), onde:\cite{Maq}

\begin{enumerate}
	\item{$\Sigma$ é um alfabeto de símbolos de entrada.} 
	\item{Q é um conjunto de estados possíveis do autômato, o qual é finito.}
	\item{$\delta$ é a função programa ou de transição}
        \item{$q_{0}$ é o estado inicial do autômato,tal que q0 é elemento de $Q$ }
        \item{F é um conjunto de estados finais tal que F está contido em Q.}
	\item{$\Delta$ é um alfabeto de símbolos de saída.}
	\item{$\delta$S é a função de saída a qual é uma função total.}
\end{enumerate} 

O processamento de uma Máquina 
de Moore ocorre da mesma forma que 
na máquina de Mealy, assim como o 
tratamento de saídas vazias. Assim como 
a Máquina de Mealy, se todos os seus 
estados gerarem saída vazia, ela também 
se comporta como um Autômato Finito. 

\subsection{Exemplos}

\subsubsection{Máquina de Mealy}

Uma aplicação comum e 
freqüentemente recomendada para os 
autômatos com saída é o projeto de 
diálogo entre um programa (de 
computador) e o seu usuário. Neste caso, 
o diálogo poderia se dar de duas 
maneiras: ser comandado pelo programa 
ou pelo usuário.

\subsubsection{Máquina de Moore}

Um exemplo comum de aplicação 
do conceito de Máquina de Moore é o 
desenvolvimento de Analisadores 
Léxicos de compiladores ou tradutores 
de linguagens em geral. Basicamente,
um analisador léxico é um Autômato 
Finito (em geral, determinístico) que 
identifica os componentes básicos da 
linguagem como, por exemplo, números, 
identificadores, separadores, etc. Uma 
Máquina de Moore como um Analisador 
Léxico é como segue:

 \begin{enumerate}
	\item{um estado final é associado a 
cada unidade léxica; } 
	\item{cada estado final possui uma 
saída (definida pela Função de Saída) 
que descreve ou codifica a unidade 
léxica identificada;}
	\item{para os demais estados (não-
finais) a saída gerada é a palavra vazia. }
\end{enumerate} 

\subsection{Equivalência entre máquinas de 
Mealy e Moore}

A equivalência dos dois modelos 
de Autômato Finito com Saída não é 
válida para a entrada vazia. Neste caso, 
enquanto a Máquina de Moore gera a 
palavra correspondente ao estado inicial, 
a Máquina de Mealy não gera qualquer 
saída, pois não executa transição 
alguma. Entretanto, para os demais 
casos, a equivalência pode ser 
facilmente mostrada. Assim, toda 
Máquina de Moore pode ser simulada 
por uma Máquina de Mealy, para 
entradas não vazias, e Toda Máquina de 
Mealy pode ser simulada por uma 
Máquina de Moore. No caso de saídas 
vazias, o que ocorre é que enquanto a 
Máquina de Moore gera a palavra 
correspondente ao estado inicial, a 
Máquina de Mealy não gera qualquer 
saída, pois não executa transição 
alguma, tornando assim as duas 
incompatíveis.

\section{Aplicação dos autômatos finitos na bioinformática} 
A teoria dos autômatos finitos tem grande utilidade na bioinformática, muitos problemas como análise, processamento, 
simulação e interpretação dedados biológicos podem ser associados com os autômatos. Como um exemplo, na detecção de padrões nas 
sequências de \textit{DNA} e aminoácidos. Outro uso comum para a bioinformatica é na comparação de saídas de sequências, assim como simulações 
e predições. Todas essas aplicações requerem algoritmos e/ou autômato.

\subsection{Problemas especifícos}

\subsubsection{Comparação de sequências}

No \textit{DNA} e aminoácidos há certos padrões em partes da sequencia que são de grande interesse para a bioinformática. Há também o interesse 
na comparação da sequencia inteira que geralmente é muito grande e ver quais transformações a sequência tem. Isso é relevante porque duas ou mais 
sequencias podem serem equivalentes sem serem idênticas. Inserções, deleções e rearranjo de nucleotídeos e aminoácidos, por exemplo, podem ocorrer. Essas 
transformações nas sequencias são possíveis e podem ocorrer naturalmente.  \cite{Bio1}

Esses problemas são diretamente aplicados a certas áreas da teoria dos autômatos. A teoria dos autômatos pode ser generalizada e aplicada para 
discernir quais algoritmos podem ser criados e quais não podem. Também pode ser usada para considerações sobre tem e espaço. Isto é relevante devido 
a “urgente  necessidade de desenvolvimento de algoritmos” para a comparação de sequências \cite{Bio1}.

\subsubsection{Detecção de padrões dentro das sequências}

O reconhecimento de padrões pode ser determinado pelo mecanismo dos autômatos porque é comparado pequenas partes da sequência ou subsequências dentro da sequencia. 
Mas há uma grande complexidade em fazer isso devido à ambiguidade e o não determinismo constantes na biologia.  \cite{Bio1}

Nesse artigo, Cohen da um exemplo de gramática que poderia ser feita para descrever a sintaxe de genes. Ele apresenta a idéia de representar um 
gene como um não terminal  nessa gramática, mas ao mesmo tempo admite que isso pode ser uma tarefa muito difícil. Também uma gramática livre de contexto pode 
ser implementada para mapear as sequências de \textit{RNA} 
em uma estrutura  bidimensional e que pode ser transformado em um autômato finito para definir a mesma linguagem.

\subsubsection{Detecção de regiões reguladoras de genes}

No cálculo para a predição das regiões reguladoras dos genes, padrões que tem significante sobre ou sub-representação dentro do genoma ou das proteínas são 
grandes candidatos para serem elementos que ajudam na expressão ou repressão de gene, também conhecidos como elementos reguladores. Com os autômatos finitos, 
é possível achar uma solução para o problema não só para achar as regiões reguladoras trabalhando em conjunto com cadeias de Markov, mas também para o tratamento 
estatístico. (PaoloRibeca andEmanueleRaineri) \cite{Bio2}

\section{Aplicação de Autômatos em Jogos}

Na área da informática sempre houve um desejo que o computador se interagisse mais com o ser humano, jogando e aprendendo com seu erros para que aumente seu desempenho. É nessa área que entra a Inteligência Artificial (IA), que nos últimos anos tem se desenvolvido bem criando programas cada vez mais humanos, atuando e tomando decisões.

No ramo dos jogos, as técnicas de IA estão bem desenvolvidas com jogos mais inteligentes e realistas. O destaque fica por conta dos Jogos de Tiro em Primeira Pessoa ou FPS (First Person Shooter). Neste, o jogador controla o personagem como se ele próprio estivesse ali, com a visão de primeira pessoa e armas para cumprir diversos tipos de missões. É nesses jogos em que os autômatos finitos entram em cena.

Um exemplo de autômato finito em um jogo de FPS é o Quake. Quando lançado, o seu código foi autorizado para ser usados por outras companhias que produziram grandes jogos provando o sucesso da técnica. \cite{game}

A Figura 8 mostra o autômato de um foguete Quake, um projétil de uma arma chamada Rocket Launcher, operada e possuída por um jogador. A figura é bem próxima de um Diagrama de Transição de Estado. As caixas numeradas por 1 representam os estados, 2 são os gatilhos e as setas são transições de estado e 3 são os pontos de entrada e saída.
\begin{figwindow}[2, c, {\includegraphics[height=7cm,width=\textwidth]{jogo.png}}, {Representação de transição de estado do projétil de foguete}]
\end{figwindow}
O diagrama representa o ciclo de vida do projétil. O \cite{game} faz uma interpretação subjetiva do código afirmando que o projétil é criado como sendo o produto de uma ação com outro autômato, chamada de Rocket Launcher em sua Ação de Tiro. Quando a instância do projeto desaparece, ela é excluída do jogo.

Quake faz um extenso uso de autômatos finitos que controlam os agentes que existem no ambiente do jogo. 

\section{Conclusão}

Com certeza, na área de Computação, a teoria de autômatos é uma ferramenta fundamental a ser compreendida. É a base de toda a linguagem e na construção de um compilador. Além disso, é empregada em outras áreas como na bioinformática e em circuitos de sistemas digitais. 

Os games também ganharam a sua contribuição, em especial nos Jogos de Tiro em Primeira Pessoa. Possibilitando assim, uma interação maior entre o jogador e o jogo.

Basicamente os autômatos finitos são determinísticos (DFA) ou não-determinísticos (NFA). No DFA, o autômato não pode estar em mais de um estado em certo momento, enquanto no NFA pode. Ambas são 5-tuplas com a diferença no seu retorno. NFA retorna um conjunto de estado e DFA retorna um único estado.

Outra classificação de autômatos finitos são os Autômatos Finitos com Movimentos Vazios. O principal aspecto está de que nesse autômato é permitida a transição para uma entrada vazia, sem símbolo de entrada.

É possível também de se chegar em DFA a partir de um NFA  que aceite a mesma linguagem.

A minimização de autômatos finitos, mesmo não diminuindo o custo na implementação, é uma grande aliada para representar um mesmo autômato finito com um menor número de estados. Para tal é necessário respeitar três regras: ser determinístico, não possuir estados inacessíveis e ser previstas transições para todos os símbolos do alfabeto a partir de qualquer estado.



\nocite{*}
\bibliographystyle{plain}
\bibliography{bibliografia}

\end{document}
